/*
 *  Copyright (C) 2011 Jaime Pavlich-Mariscal
 * 
 *  This program is free software: you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation, either version 3 of the License, or
 *  (at your option) any later version.
 * 
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 * 
 *  You should have received a copy of the GNU General Public License
 *  along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */
package cl.ucn.disc.biblio.refcluster;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Comparator;
import java.util.Iterator;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Set;
import java.util.TreeSet;
import org.apache.log4j.Logger;
import org.jgrapht.UndirectedGraph;
import org.jgrapht.alg.BronKerboschCliqueFinder;
import org.jgrapht.graph.DefaultEdge;
import org.jgrapht.graph.SimpleGraph;

/**
 *
 * @author Jaime Pavlich-Mariscal
 */
public class Clusterer {

    public static final Logger LOGGER = Logger.getLogger(ReferenceClusterer.class.getName());
    private final Comparator<Set<?>> setSizeComparator = new Comparator<Set<?>>() {

        @Override
        public int compare(Set<?> o1, Set<?> o2) {
            // Puts first the biggest sets and last the smallest sets
            if (o1.size() > o2.size()) {
                return -1;
            } else if (o1.size() < o2.size()) {
                return 1;
            }
            return 0;
        }
    };

    /**
     * Creates an undirected graph where the nodes are {@link Matchable} instances
     * and the edges connect two nodes if they match using
     * {@link Matcher#matches(cl.ucn.disc.biblio.refcluster.Matchable, cl.ucn.disc.biblio.refcluster.Matchable) }
     * @param <T>
     * @param matchables Set of objects t
     * @param matcher
     * @return
     */
    public <T extends Matchable> UndirectedGraph<T, DefaultEdge> createMatchGraph(List<T> matchables, Matcher<T> matcher) {
        UndirectedGraph<T, DefaultEdge> g = new SimpleGraph<T, DefaultEdge>(DefaultEdge.class);
        for (T s : matchables) {
            g.addVertex(s);
        }
        for (int i = 0; i < matchables.size(); i++) {
            for (int j = i + 1; j < matchables.size(); j++) {
                T m1 = matchables.get(i);
                T m2 = matchables.get(j);
                // Creates an edge only if it does not exist and the matchables match, but are not equal
                // (i.e., avoids creation of self-referencing edges)
                if (g.getEdge(m1, m2) == null && matcher.matches(m1, m2) && !m1.equals(m2)) {
                    g.addEdge(m1, m2);
                }
            }
        }
        return g;
    }

    public <T extends Matchable> Collection<Set<T>> findEquivalenceClasses(List<T> list, Matcher<T> matcher) {

        UndirectedGraph<T, DefaultEdge> g = createMatchGraph(list, matcher);
        Collection<Set<T>> authorClusters = findEquivalenceClasses(g);
        return authorClusters;
    }

    /**
     * Creates equivalence classes based on an undirected match graph. It finds
     * all of its maximal non-intersecting cliques.
     *
     * @param <T>
     * @param g
     * @return
     */
    private <T extends Matchable> Collection<Set<T>> findEquivalenceClasses(UndirectedGraph<T, DefaultEdge> g) {
        BronKerboschCliqueFinder<T, DefaultEdge> cf = new BronKerboschCliqueFinder<T, DefaultEdge>(g);
        Collection<Set<T>> cliques = cf.getAllMaximalCliques();

        // Obtain only those cliques that do not intersect with others, to avoid
        // ambiguities in author/journal names
        Collection<Set<T>> clusters = findNonIntersectingCliques(cliques);

        // Removes clusteres with one element
        Iterator<Set<T>> it = clusters.iterator();
        while (it.hasNext()) {
            Set<T> cluster = it.next();
            if (cluster.size() <= 1) {
                it.remove();
            }
        }

        return clusters;
    }

    private <T extends Matchable> Collection<Set<T>> findNonIntersectingCliques(Collection<Set<T>> cliques) {
        // Creates a graph of intersecting cliques
        UndirectedGraph<Set<T>, DefaultEdge> g = createMatchableSetIntersectionGraph(cliques);

        // Sorts cliques by size, from larger to smaller.
        PriorityQueue<Set<T>> sortedCliques = new PriorityQueue<Set<T>>(10, setSizeComparator);
        sortedCliques.addAll(g.vertexSet());

        // Adds to the result collection all of those cliques that: (a) have no
        // other intersecting cliques or
        // (b) are the biggest among their intersecting cliques
        Collection<Set<T>> result = new ArrayList<Set<T>>();
        Set<Set<T>> excludedCliques = new LinkedHashSet<Set<T>>();
        for (Set<T> s : sortedCliques) {
            if (g.edgesOf(s).isEmpty()) {
                result.add(s);
            } else if (!excludedCliques.contains(s)) {
                result.add(s);
                for (DefaultEdge edge : g.edgesOf(s)) {
                    Set<T> s1 = g.getEdgeSource(edge);
                    Set<T> s2 = g.getEdgeTarget(edge);
                    if (s1 != s) {
                        excludedCliques.add(s1);
                    }
                    if (s2 != s) {
                        excludedCliques.add(s2);
                    }
                }
            }
        }
        return result;
    }

    /**
     * Creates a graph where nodes are sets of {@link Matchable} and edges between two
     * sets indicate that they intersect.
     *
     * @param <T>
     * @param sets
     * @return An undirected graph
     */
    private <T extends Matchable> UndirectedGraph<Set<T>, DefaultEdge> createMatchableSetIntersectionGraph(Collection<Set<T>> collectionOfSets) {
        List<Set<T>> sets = new ArrayList<Set<T>>(collectionOfSets);
        UndirectedGraph<Set<T>, DefaultEdge> g = new SimpleGraph<Set<T>, DefaultEdge>(DefaultEdge.class);
        for (Set<T> s : sets) {
            g.addVertex(s);
        }
        for (int i = 0; i < sets.size(); i++) {
            for (int j = i + 1; j < sets.size(); j++) {
                Set<T> s1 = sets.get(i);
                Set<T> s1Tmp = new TreeSet<T>(s1);
                Set<T> s2 = sets.get(j);
                s1Tmp.retainAll(s2);
                if (!s1Tmp.isEmpty()) {
                    g.addEdge(s1, s2);
                }
            }
        }
        return g;
    }
}
